﻿//中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
//
//例如 arr = [2, 3, 4] 的中位数是 3 。
//例如 arr = [2, 3] 的中位数是(2 + 3) / 2 = 2.5 。
//实现 MedianFinder 类 :
//MedianFinder() 初始化 MedianFinder 对象。
//void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
//double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10 - 5 以内的答案将被接受。
//
//输入
//	["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//	[[], [1], [2], [], [3], []]
//输出
//	[null, null, null, 1.5, null, 2.0]
//
//解释
//	MedianFinder medianFinder = new MedianFinder();
//	medianFinder.addNum(1);    // arr = [1]
//	medianFinder.addNum(2);    // arr = [1, 2]
//	medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//	medianFinder.addNum(3);    // arr[1, 2, 3]
//	medianFinder.findMedian(); // return 2.0
//
//提示:
//	-10^5 <= num <= 10^5
//	在调用 findMedian 之前，数据结构中至少有一个元素
//	最多 5 * 10^4 次调用 addNum 和 findMedian

class MedianFinder {
    priority_queue<int> left; // ⼤根堆

    priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆

public:
    MedianFinder() {}
    void addNum(int num) {
        // 分类讨论即可

        if (left.size() == right.size()) // 左右两个堆的元素个数相同

        {
            if (left.empty() || num <= left.top()) // 放left⾥⾯

            {
                left.push(num);
            }
            else {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else {
            if (num <= left.top()) {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else {
                right.push(num);
            }
        }
    }

    double findMedian() {
        if (left.size() == right.size())
            return (left.top() + right.top()) / 2.0;
        else
            return left.top();
    }
};
/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */